package 中等.搜索.回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串
 * 都是 回文串 。返回 s 所有可能的分割方案。
 * 回文串 是正着读和反着读都一样的字符串。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/palindrome-partitioning/
 */
public class 分割回文串_131 {

    public static void main(String[] args) {

        System.out.println(new 分割回文串_131().partition("aab"));

    }

    public List<List<String>> partition(String s) {
        List<List<String>> lists = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            List<String> list = new ArrayList<>();
            if (isHuiWen(0, i, s)) {
                list.add(s.substring(0, i + 1));
                dfs(i + 1, s, list, lists);
            }
        }
        return lists;
    }

    // 递归查找 [left,s.length()-1] 的分割回文串方案有多少
    private void dfs(int left, String s, List<String> list, List<List<String>> lists) {
        if (left == s.length()) {
            lists.add(list);
        }
        for (int i = left; i < s.length(); i++) {
            if (isHuiWen(left, i, s)) {
                // 需要 new 一个新的list，这一层的递归，不能影响下次遍历的递归结果
                List<String> nextList = new ArrayList<>();
                nextList.addAll(list);
                nextList.add(s.substring(left, i + 1));
                dfs(i + 1, s, nextList, lists);
            }
        }
    }

    // 判断 [left,right] 是否是回文串
    // TODO 优化，采用动态规划预处理 s 所有的子回文字符串
    private boolean isHuiWen(int left, int right, String s) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

}
